package com.shuang.backtracking6;

import java.util.ArrayList;
import java.util.List;

public class Partition {
    //全局变量
    //存结果
    List<List<String>> res = new ArrayList<>();
    //存回文子串
    List<String> str = new ArrayList<>();

    public List<List<String>> partition(String s) {

        backTracking(s, 0, new StringBuilder());

        return res;
    }

    private void backTracking(String s, int startIndex, StringBuilder sb) {

        //终止条件
        if (startIndex >= s.length()) {
            res.add(new ArrayList(str));
            return;
        }

        //for 循环
        for (int i = startIndex; i < s.length(); i++) {
            //拼接字符串
            sb.append(s.charAt(i));
            //判断是否是回文串 是的话存到str
            if (check(sb)) {

                str.add(sb.toString());

                //递归
                backTracking(s, i + 1, new StringBuilder());

                //回溯
                str.remove(str.size() - 1);
            }
        }
    }

    //判断字符串是否是回文串
    private boolean check(StringBuilder sb) {
        for (int i = 0; i < sb.length() / 2; i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }
}
